package demo6;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-08-05
 * Time: 7:47
 */
public class Test {

    static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node parent;

        public Node(int val){
            this.val = val;
        }
    }

    //找到某一个节点的后继结点
    public static Node getSuccessorNode(Node node){
        if(node==null) return null;//如果节点为null,没有后继结点
        Node parent = null;
        if(node.right!=null){
            //如果该节点有右树,那它的后继结点就是右树上的最左节点
            node = generateNode(node.right);
            return node;
        }else {
            //否则一直沿着父亲这条线走,一直到parent为null或者parent是某个节点的左孩子
            parent = node.parent;
            while(parent!=null&&parent.right==node){
                //保持父亲不为null,并且我是父亲的右孩子
               node = parent;
               parent = node.parent;
            }
        }
        return parent;
    }
    private static Node generateNode(Node parent){
        if(parent==null) return null;
          //一直找到这个节点的最左
        while(parent.left!=null){
            parent = parent.left;
        }
        return parent;
    }


    public static void main(String[] args) {

    }

}
